#ifndef AllSSPBinomial_CPP
#define AllSSPBinomial_CPP

#include<limits.h>
#include"AdjacencyList.cpp"
#include"BinomialHeap.cpp"

//int getMinimum (unsigned int arr[], unsigned int visited[], unsigned int num);

class EdgeNodeBinomial
{
public:
    unsigned int vertex1;
    unsigned int vertex2;
    unsigned int cost;
    EdgeNodeBinomial* next;
    BinomialHeapNode<EdgeNodeBinomial>* pointerToNodeInHeap;

    EdgeNodeBinomial()
    {
        this->resetNode();
    }

    EdgeNodeBinomial(unsigned int vertex1, unsigned int vertex2, unsigned int cost)
    {
        this->init (vertex1, vertex2, cost);
    }

    void init(unsigned int vertex1, unsigned int vertex2, unsigned int cost)
    {
        this->vertex1 = vertex1;
        this->vertex2 = vertex2;
        this->cost = cost;
        this->next = NULL;
        this->pointerToNodeInHeap = NULL;
    }

    void resetNode()
    {
        this->vertex1 = 0;
        this->vertex2 = 0;
        this->cost = 0;
        this->next = NULL;
        this->pointerToNodeInHeap = NULL;
    }

    void display ()
    {
        cout<<"\nEdgeNodeBinomial:: ("<<this->vertex1<<", "<<this->vertex2<<", "<<this->cost<<")\t AddressToHeapNode: "<<pointerToNodeInHeap;
    }
};

class AllSSPBinomial
{
    static const int maxNumberOfNodes = 500;
    AdjacencyList* list;
    BinomialHeap<EdgeNodeBinomial>* heap;
    unsigned int visited[AllSSPBinomial::maxNumberOfNodes];

private:
    int distMatrixSize;
    EdgeNodeBinomial* freeNodes;
    int numberOfFreeNodes;
    void releaseNode (EdgeNodeBinomial* node);
    EdgeNodeBinomial* getFreeNode(unsigned int vertex1, unsigned int vertex2, unsigned int cost);

    void deleteAllFreeNodes();
    void initializeFreeNodes();
    void initializeBinomialHeap(unsigned int source, BinomialHeap<EdgeNodeBinomial>* heap);

public:
    void deleteDistMatrix();
    EdgeNodeBinomial* dist[AllSSPBinomial::maxNumberOfNodes][AllSSPBinomial::maxNumberOfNodes];
    void init(AdjacencyList* list);
    AllSSPBinomial(AdjacencyList* list);
    AllSSPBinomial();
    ~AllSSPBinomial();
    void computeShortestPath();
    void display();
};

void AllSSPBinomial::display()
{
    cout<<"\n\nPrinting min distances"<<endl;
    for (unsigned int i=0; i<this->distMatrixSize; i++)
    {
        for (unsigned int j=0; j<this->distMatrixSize; j++)
        {
            if (dist[i][j]->cost == std::numeric_limits<unsigned int>::max())
            {
                cout<<"\tInf.";
            }
            else
            {
                cout<<"\t"<<dist[i][j]->cost;
            }
        }
        cout<<endl;
    }
}

void AllSSPBinomial::computeShortestPath()
{
    //cout<<"maxNode"<<list->getNumberOfNodes();
    for (unsigned int i=0; i<this->distMatrixSize; i++)
    {
        heap->emptyIt();
        this->initializeBinomialHeap(i, heap);
        //heap->displayBFS();

        for (unsigned int ii=0; ii<this->distMatrixSize; ii++)
        {
            visited[ii] = 0;
        }
        visited[i] = 1;
        dist[i][i]->cost = 0;
        EdgeNodeBinomial* minVertex;
        while ((minVertex = heap->removeMin()) != NULL)
        {
            visited[minVertex->vertex2] = 1;
            AdjacencyListNode* temp = this->list->getAdjacencyListNode(minVertex->vertex2);
            if (temp == NULL)
            {
                continue;
            }
            QueueNode<AdjacencyNode>* temp1 = temp->adjacentNodes.getHead();
            while (temp1 != NULL)
            {
                AdjacencyNode* node = temp1->val;
                if (visited[node->vertex] == 0 && dist[i][node->vertex]->cost > minVertex->cost + node->cost)
                {
                    if (dist[i][node->vertex]->pointerToNodeInHeap == NULL)
                    {
                        EdgeNodeBinomial* tempNode = dist[i][node->vertex];
                        tempNode->cost = minVertex->cost + node->cost;
                        heap->insert(tempNode, &(tempNode->cost), &(tempNode->pointerToNodeInHeap));
                    }
                    else
                    {
                        heap->decreaseKey(dist[i][node->vertex]->pointerToNodeInHeap, minVertex->cost + node->cost);
                    }
                }
                temp1 = temp1->next;
            }
        }
    }
}

//could be optimized
void AllSSPBinomial::initializeBinomialHeap(unsigned int source, BinomialHeap<EdgeNodeBinomial>* heap)
{
    QueueNode<AdjacencyListNode>* temp = this->list->adjacencyListImp.getHead();
    //this->list->display();
    QueueNode<AdjacencyNode>* temp1 = NULL;
    while (temp != NULL)
    {
        AdjacencyListNode* node = temp->val;
        unsigned int vertex1 = node->vertex;
        if (vertex1 == source)
        {
            temp1 = node->adjacentNodes.getHead();
            break;
        }
        temp = temp->next;
    }
    while (temp1 != NULL)
    {
        unsigned int vertex1 = source;
        AdjacencyNode* node2 = temp1->val;
        unsigned int vertex2 = node2->vertex;
        unsigned int cost = node2->cost;
        EdgeNodeBinomial* tempNode = dist[vertex1][vertex2];
        tempNode->cost = cost;
        heap->insert(tempNode, &(tempNode->cost), &(tempNode->pointerToNodeInHeap));
        //cout<<"("<<vertex1<<","<<vertex2<<","<<cost<<")\t";
        temp1 = temp1->next;
    }
}

void AllSSPBinomial::init(AdjacencyList* list)
{
    //delete[] visited;
    //visited = NULL;
    this->deleteDistMatrix();
    this->list = list;
    this->distMatrixSize = this->list->getNumberOfNodes();
    //initializing dist matrix
    //this->dist = (EdgeNodeBinomial***)new EdgeNodeBinomial**[this->distMatrixSize];
    for (unsigned int i=0; i<this->distMatrixSize; i++)
    {
        //this->dist[i] = (EdgeNodeBinomial**)new EdgeNodeBinomial*[this->distMatrixSize];
        for (unsigned int j=0; j<this->distMatrixSize; j++)
        {
            EdgeNodeBinomial* tempNode = this->getFreeNode(i, j, std::numeric_limits<unsigned int>::max());   //new EdgeNodeBinomial(i, j, std::numeric_limits<unsigned int>::max());
            this->dist[i][j] = tempNode;
        }
    }
    //visited = new unsigned int [this->distMatrixSize];
}

AllSSPBinomial::AllSSPBinomial(AdjacencyList* list)
{
    this->list = NULL;
    this->initializeFreeNodes();
    this->init (list);
    heap = new BinomialHeap<EdgeNodeBinomial>();
}

AllSSPBinomial::AllSSPBinomial()
{
    this->list = NULL;
    this->heap = new BinomialHeap<EdgeNodeBinomial>();
    this->initializeFreeNodes();
}

void AllSSPBinomial::initializeFreeNodes()
{
    this->freeNodes = NULL;
    this->numberOfFreeNodes = AllSSPBinomial::maxNumberOfNodes * AllSSPBinomial::maxNumberOfNodes;
    for (int i=0; i<AllSSPBinomial::maxNumberOfNodes; i++)
    {
        for (int j=0; j<AllSSPBinomial::maxNumberOfNodes; j++)
        {
            EdgeNodeBinomial* temp = new EdgeNodeBinomial();
            temp->next = this->freeNodes;
            this->freeNodes = temp;
        }
    }
}

EdgeNodeBinomial* AllSSPBinomial::getFreeNode(unsigned int vertex1, unsigned int vertex2, unsigned int cost)
{
    EdgeNodeBinomial* temp = this->freeNodes;
    this->freeNodes = this->freeNodes->next;
    temp->init (vertex1, vertex2, cost);
    temp->next = NULL;
    this->numberOfFreeNodes--;
    return temp;
}

void AllSSPBinomial::releaseNode (EdgeNodeBinomial* node)
{
    node->resetNode();
    node->next = this->freeNodes;
    this->freeNodes = node;
    this->numberOfFreeNodes++;
}

void AllSSPBinomial::deleteAllFreeNodes()
{
    while (this->freeNodes != NULL)
    {
        EdgeNodeBinomial* temp = this->freeNodes;
        this->freeNodes= this->freeNodes->next;
        delete (temp);
    }
}

AllSSPBinomial::~AllSSPBinomial()
{
    this->deleteDistMatrix();
    this->deleteAllFreeNodes();
    //delete[] visited;
    delete heap;
}

void AllSSPBinomial::deleteDistMatrix()
{
    if (this->list == NULL)
    {
        return;
    }
    int numberOfNodes = this->distMatrixSize;
    for (unsigned int i=0; i<numberOfNodes; i++)
    {
        for (unsigned int j=0; j<numberOfNodes; j++)
        {
            if (dist[i][j] != NULL)
            {
                this->releaseNode (dist[i][j]);
                dist[i][j] = NULL;
                //delete dist[i][j];
            }
        }
        /*if (dist[i] != NULL)
        {
            delete[] dist[i];
        }*/
    }
    /*if (dist != NULL)
    {
        delete[] dist;
    }*/
}

#endif

